\chapter{ Fundamentos de reconocimiento de formas}

\section{Introducci\'on}


El reconocimiento de formas (RF) es una disciplina que estudia c\'omo construir sistemas autom\'aticos, capaces de emular aspectos perceptivos propios del comportamiento humano~\cite{duda73,fukunaga90}. El t\'ermino \emph{reconocer} equivale a clasificar en $C$ clases o categor\'ias los distintos objetos observados. Por ejemplo, dada una mamograf\'ia, podr\'ia pedirse a un sistema de RF que la clasifique en uno de las cuatro categor\'ias de densidades establecidas por BI-RADS.

La llamada \textbf{aproximaci\'on inductiva} al RF requiere del uso de un conjunto de muestras de aprendizaje, que son utilizadas para crear un modelo. Posteriormente, un clasificador usar\'a este modelo para identificar (clasificar) objetos no vistos durante la etapa de aprendizaje. La aproximaci\'on inductiva lleva asociada impl\'icitamente el concepto de aprendizaje.

\section{Esquema de un sistema de reconocimiento}

En la Figura~\ref{fig:esquema_RF} se muestra el esquema de un sistema de RF inductivo. El sistema puede trabajar en modo aprendizaje o en modo clasificaci\'on. En ambos casos se comienza con la adquisici\'on de un objeto del mundo real (por ejemplo, captura de una imagen). A continuaci\'on se realiza un preproceso cuyo objetivo es realzar y acondicionar los objetos de inter\'es. Seguidamente, en la etapa de obtenci\'on de caracter\'isticas se realizan ciertas medidas sobre el objeto que se desea analizar. La idea es obtener una serie de valores num\'ericos o s\'imbolos (vector de caracter\'isticas) representativos del objeto. Esta etapa es crucial, ya que dependiendo del tipo de caracter\'isticas con las que trabajemos, ser\'a m\'as o menos viable discriminar entre objetos de distintas clases. Finalmente, dependiendo de si se trabaja en modo aprendizaje o en modo clasificaci\'on, estas caracter\'isticas se utilizar\'an bien para aprender (entrenar) un modelo, bien para clasificar el objeto observado en una de las $C$ posibles clases, teniendo en cuenta el modelo aprendido.

\begin{figure}[ht]
\centering
  \includegraphics[width=1\columnwidth]{esquema_RF}
  \caption{% 
  \label{fig:esquema_RF} 
  Esquema de un sistema de reconocimiento de formas.}
\end{figure}

Existen distintas aproximaciones a la hora de dise\~nar el modelo que
representa los objetos de nuestro problema.  En la \textbf{aproximaci\'on estad\'istica}~\cite{hastie01}, los objetos se representan en forma de $n$ caracter\'isticas o medidas, conocidas como \emph{vector de caracter\'isticas}. Estos vectores pueden verse como un punto en un espacio de $n$ dimensiones. El objetivo es escoger aquellas caracter\'isticas que permitan distribuir los vectores de caracter\'isticas (puntos) de manera que las distintas clases o categor\'ias ocupen regiones en el espacio $n$-dimensional lo m\'as compactas y disjuntas posible. Con ello, se establecen unas \emph{fronteras de decisi\'on} en el espacio de caracter\'isticas que tratan de separar los vectores de cada clase.  Estas fronteras de decisi\'on se determinan a partir de las distribuciones de probabilidad de los vectores de caracter\'isticas de cada clase, obtenidos de las muestras de aprendizaje. Durante la etapa de clasificaci\'on, ante una muestra desconocida (muestra de test), \'esta se clasificar\'a en una clase u otra en funci\'on de la posici\'on que ocupe respecto a las fronteras de decisi\'on.

Existen multitud de t\'ecnicas estad\'isticas para definir las fronteras de decisi\'on y realizar la clasificaci\'on. Las prestaciones del sistema de RF depender\'a, entre otros factores, del clasificador dise\~nado y del tipo de caracter\'isticas empleadas. A continuaci\'on se resumen algunas de las t\'ecnicas empleadas por distintos autores en relaci\'on a la clasificaci\'on de la densidad mamaria.

%\section{Esquema de un sistema de reconocimiento}
\subsection{Adquisici\'on de datos}
En esta primera etapa se mide un objeto del mundo real mediante los sensores f\'isicos apropiados, por ejemplo, una c\'amara de v\'ideo para la captura de im\'agenes o un micr\'ofono para registrar la voz. En muchos casos esta informaci\'on se presenta en forma de se\~nal anal\'ogica, la cual puede ser preprocesada para mejorar su calidad o para aislar la parte \'util de la misma. Una posterior digitalizaci\'on de la se\~nal permite que \'esta pueda ser tratada por un computador, bien para almacenarla en alg\'un tipo de soporte permanente, bien para utilizarla directamente como entrada en la etapa posterior. Se dice que la se\~nal obtenida pertenece al espacio de representaci\'on primario.

\subsection{Preprocesado}

La funci\'on del modulo de preprocesamiento, tambi\'en llamado de tratamiento de la se\~nal, es, b\'asicamente, realzar y acondicionar el patr\'on de inter\'es respecto del resto de la se\~nal. En el caso particular de que la se\~nal de entrada represente una imagen (tal es el caso del presente trabajo), ser\'an operaciones habituales de esta etapa el escalado, cuantificaci\'on, filtrado, modificaciones del histograma, transformaciones geom\'etricas, operaciones morfol\'ogicas, eliminaci\'on de ruido y segmentaci\'on. Adem\'as, cuando el m\'odulo de preprocesamiento opera en modo de entrenamiento, se realizar\'a el etiquetado del patr\'on para permitir su posterior identificaci\'on. Buena parte de estas operaciones son materia de un campo de trabajo particular como es el del tratamiento digital de im\'agenes, sobre el que existe
extensa literatura [Jain 89, Gonz 99].

\subsection{Extracci\'on de caracter\'isticas}
Las caracter\'isticas de un objeto son el resultado de aplicar ciertas funciones sobre las medidas obtenidas del objeto (se\~nal digital acondicionada), que ayudan de alguna manera a distinguir la clase a la cual pertenece y que ser\'an utilizadas como entrada al clasificador. La obtenci\'on de caracter\'isticas incluye los procesos de extracci\'on, selecci\'on y reducci\'on de caracter\'isticas. El objetivo de esta etapa es encontrar el conjunto de caracter\'isticas que mejor representa el objeto de entrada, esto es, que minimice las diferencias intraclase y maximice las diferencias interclase. Cuando se trabaja en modo entrenamiento, es habitual realizar diversas iteraciones sobre este m\'odulo para tratar de optimizar las prestaciones del sistema.

En la fase de test se aplicar\'an los mismos m\'etodos de extracci\'on y/o selecci\'on escogidos durante el entrenamiento. La obtenci\'on de caracter\'isticas es la parte menos sistem\'atica del proceso y tiene una gran dependencia del tipo de tarea a realizar.

Normalmente, la experiencia y la intuici\'on del dise\~nador del sistema ser\'a de gran relevancia a la hora de resolver con \'exito esta etapa.

Se han considerado tres tareas en el proceso de obtenci\'on de caracter\'isticas: la
extracci\'on, que hace referencia a la transformaci\'on de la se\~nal del dominio primario a un dominio m\'as adecuado para tratar el problema; la selecci\'on, con la que se escogen aquellas caracter\'isticas que aportan informaci\'on valiosa para la identificaci\'on del objeto, desechando la informaci\'on no discriminante o redundante; y la reducci\'on del n\'umero de caracter\'isticas, que contribuir\'a a reducir el coste computacional.

\subsection{Entrenamiento o aprendizaje}

El clasificador se entrena tratando de particionar el espacio de caracter\'isticas
generado por el m\'odulo anterior, con el objetivo de minimizar el error de clasificaci\'on entre los prototipos del conjunto de evaluaci\'on. La retroalimentaci\'on hacia los m\'odulos anteriores permite al dise\~nador del sistema escoger, entre las distintas t\'ecnicas probadas, aquella que mejor rendimiento proporcione, atendiendo a los resultados obtenidos al clasificar el conjunto de evaluaci\'on.

\subsection{Clasificaci\'on}

En la fase de test, el clasificador toma el vector de caracter\'isticas extra\'ido del patr\'on de entrada y le asigna la clase con la que se encuentra una mayor similitud, de acuerdo al modelo inducido durante el entrenamiento. En ocasiones la salida del clasificador no se limita a la clase m\'as similar y puede ofrecer m\'ultiples hip\'otesis en forma de lista de n-tuplas conteniendo el identificador del objeto, una etiqueta de clase (hip\'otesis) y el nivel de fiabilidad asignado a la hip\'otesis.

\section{Clasificador basado en distancia}

\subsection{Distancia geom\'etrica entre muestras}

Los sistemas de clasificaci\'on basados en distancia se basan de la distancia eucl\'idea entre la muestra bajo estudio y las muestras del conjunto de entrenamiento para determinar la clase ganadora.

Sea $x_i$ una muestra de entrada compuesta por un vector de $D$ dimensiones ($j=1, 2, \dots, D$) perteneciente a un conjunto de $N$ muestras de entrada ($i=1, 2, \dots, N$), se define la distancia eucl\'idea entre dicha muestra y una muestra cualquiera del conjunto de entrenamiento $x_t$ seg\'un se muestra en la ecuaci\'on \ref{eq:knn_euclidean_distance}.

\begin{equation}
d(x_i,x_t)= \sqrt{\sum_{j=1}^{D} (x_{ij}-x_{tj})^2}
\label{eq:knn_euclidean_distance}
\end{equation}

\subsubsection{El clasificador del vecino m\'as cercano}
\label{sec:classifier_nn}

El concepto de vecino m\'as cercano (\emph{nearest neighbor}) en clasificadores basados en distancia hace referencia a la muestra de entrenamiento que presenta la m\'inima distancia eucl\'idea con respecto a la muestra de entrada que se desea clasificar.

Las celda de Voronoi $R_i$, tambi\'en conocida como celda de Dirichlet, se define como la regi\'on tal que cualquier punto $x$ contenido en ella tiene como vecino m\'as cercano a la muestra $i$ del conjunto de entrenamiento. En otras palabras es la zona dentro de la cu\'al un punto $x$ est\'a m\'as cerca de un punto $i$ que de cualquier punto $m$ (ver ecuaci\'on \ref{eq:voronoi_cell}).

\begin{equation}
R_i=\{ x \in \mathbb{R}^D : d(x,x_i) \leq d(x,x_m), \forall i \neq m \}
\label{eq:voronoi_cell}
\end{equation}

En la figura \ref{fig:voronoi_cells} se muestran de manera gr\'afica dos ejemplos de conjunto de muestras junto con sus regiones de Voronoi.

\begin{figure}[!h]
\centering
\includegraphics[width=0.45\columnwidth]{voronoi_cells.png}
\includegraphics[width=0.45\columnwidth]{voronoi_cells2.png}
\caption{Ejemplo de celdas de Voronoi }
\label{fig:voronoi_cells}
\end{figure}

Por tanto, la regla de clasificaci\'on del vecino m\'as cercano consiste en otorgar a la muestra bajo estudio la etiqueta de clase de su vecino m\'as pr\'oximo.

\subsection{El clasificador $k$-NN}

El clasificador $k$-NN o clasificador de los $k$ vecinos m\'as cercanos, desarrollado inicialmente por Fix y Hodges en 1951, es uno de los m\'etodos m\'as simples y efectivos de clasificaci\'on cuando no existe conocimiento previo de la distribuci\'on de los datos de entrada.

El algoritmo se basa en el mismo principio que el algoritmo del vecino m\'as pr\'oximo extrapolando la clasificaci\'on a un sistema de votaci\'on donde se decide la clase ganadora como la clase m\'as votada entre los $k$ vecinos m\'as cercanos. 

\begin{equation}
x \in w_i \mbox{ si } k_i = max_m(k_m)
\label{eq:winner_class}
\end{equation}

El caso extremo $k=1$ corresponde con el algoritmo $nearest-neighbor$ descrito en la secci\'on anterior (\ref{sec:classifier_nn}).

\subsubsection{B\'usqueda aproximada de los $k$ vecinos m\'as cercanos}
\subsubsection{Coste de la b\'usqueda}
\subsubsection{B\'usqueda r\'apida de los k-NN mediante kd-trees}

El clasificador de los k-vecinos más cercanos ha dado buenos resultados en
muchas tareas de reconocimiento de formas. Sin embargo, plantea la desventaja de
requerir un número de prototipos muy elevado para obtener buenas prestaciones.
Manejar estos conjuntos extensos de prototipos lleva asociado, inevitablemente, un coste espacial y sobretodo temporal, nada despreciable, ya que los prototipos deben almacenarse y es necesario calcular, para cada punto de test, las distancias a todos los prototipos de la muestra. Ello hace que éste sea un método lento. En este sentido, se han propuesto diversos métodos que tratan de minimizar estos inconvenientes como es el método de búsqueda rápida aproximada basado en árboles k-dimensionales o kd-trees



\subsubsection{An\'alisis de prestaciones con \emph{cross-validation}}

La t\'ecnica de validaci\'on cruzada o \emph{cross-validation} surge de la imposibilidad de utilizar muestras del conjunto de entrenamiento para validar o testear las prestaciones del clasificador.

La utilizaci\'on de esta t\'ecnica implica la divisi\'on del conjunto total de muestras en $k$ particiones $D_1, D_2, \dots, D_k$  (\emph{$k$-fold cross-validation}) de manera que se realice un experimento de clasificaci\'on por cada conjunto ($i=1, 2, \dots, k$) utilizando en cada caso el resto de particiones como conjunto de entrenamiento.

De esta manera se nos permite la utilizaci\'on de todas las muestras disponibles para la validaci\'on del clasificador manteniendo la regla que dicta que las muestras de test deben estar fuera del proceso de entrenamiento.


\section{Reducci\'on de la dimensionalidad}

En algunas ocasiones puede ocurrir que el n\'umero de caracter\'isticas obtenido
para representar los objetos de nuestro problema sea excesivo de cara a una posterior etapa de clasificaci\'on. B\'asicamente existen dos motivos principales por los que podr\'ia ser interesante trabajar con dimensionalidades m\'as bajas (menor n\'umero de caracter\'isticas): reducir el coste computacional (tanto espacial como temporal) y mejorar la tasa de aciertos. Cuanto menor sea la dimensionalidad de los puntos a clasificar, m\'as r\'apido ser\'a el clasificador y menos memoria requerir\'a. 
Por otro lado, como se ver\'a m\'as adelante, un n\'umero de caracter\'isticas excesivamente alto puede provocar, parad\'ojicamente, una p\'erdida de precisi\'on en el clasificador. Aunque, ciertamente, reducir el n\'umero de caracter\'isticas puede implicar una p\'erdida de poder de discriminaci\'on y, consecuentemente, una reducci\'on en la precisi\'on del clasificador, tambi\'en debe tenerse en cuenta que la inclusi\'on de caracter\'isticas redundantes o carentes de informaci\'on discriminatoria puede provocar que dos muestras cualesquiera acaben siendo similares si son codificadas con un n\'umero excesivo de este tipo de caracter\'isticas [Wata 85]. Es necesario, por tanto, encontrar el n\'umero de caracter\'isticas \'optimo que maximice la precisi\'on del clasificador, al tiempo que minimice los costes computacionales a valores aceptables.

\subsection{La maldici\'on de la dimensionalidad}

El funcionamiento de un clasificador depende, entre otros factores, de la rela-
ci\'on entre el tama\~no del conjunto de muestras de entrenamiento y el n\'umero de
caracter\'isticas de dichas muestras. Por ejemplo, una t\'ecnica sencilla como table lookup que particiona el espacio de caracter\'isticas en celdas y asocia a cada una de estas celdas una etiqueta de clase, requiere un n\'umero de muestras de entrenamiento exponencial respecto a la dimensi\'on de dichas muestras [Bish 95]. Este
fen\'omeno se conoce como “maldici\'on de la dimensionalidad”.

Es sabido que la probabilidad de que una regla de decisi\'on clasifique err\'oneamente una muestra de test no se incrementa con el n\'umero de caracter\'isticas, siempre y cuando las densidades condicionales de cada clase sean totalmente conocidas (o, lo que ser\'ia equivalente, que el n\'umero de muestras de entrenamiento sea suficientemente extenso y representativo de las densidades subyacentes).

Sin embargo, es dif\'icil llegar a tener un conocimiento preciso de las densidades
condicionales de clase, por lo que en la pr\'actica se observa que tener un exceso de caracter\'isticas puede degradar las prestaciones del clasificador si el n\'umero de muestras usado para dise\~narlo es peque\~no en relaci\'on al n\'umero de caracter\'isticas [Jain 82, Raud 91, Raud 97]. La causa de este fen\'omeno radica en que a medida que crece el n\'umero de caracter\'isticas, la dispersi\'on de los puntos aumenta
exponencialmente, con lo que los par\'ametros quedan peor estimados.

\subsection{Selecci\'on de caracter\'isticas}

Tal y como se ha explicado, usar un n\'umero excesivo de caracter\'isticas puede
degradar las prestaciones del clasificador debido al fen\'omeno de la maldici\'on de la dimensionalidad. Por otro lado, es evidente que un n\'umero escaso de caracter\'isticas puede producir una p\'erdida del poder de discriminaci\'on y, consecuentemente, reducir igualmente el rendimiento del clasificador. Existe la necesidad, por tanto, de obtener un conjunto de caracter\'isticas cuanto m\'as reducido mejor, pero que al mismo tiempo recoja la informaci\'on suficiente para caracterizar las distintas clases de nuestro problema.

Dado un conjunto de caracter\'isticas extra\'ido de una muestra de test, los m\'etodos de selecci\'on de caracter\'isticas tratan de detectar y rechazar aquellas caracte-
r\'isticas que presentan un bajo o nulo poder discriminatorio. Con ello, adem\'as de
mejorar las prestaciones del clasificador, se consigue reducir costes computacionales. Habr\'ia que aclarar la diferencia entre selecci\'on y extracci\'on de caracter\'isticas. El t\'ermino selecci\'on de caracter\'isticas se refiere a algoritmos que tratan de seleccionar el mejor subconjunto de caracter\'isticas entre el conjunto de caracter\'isticas de entrada previamente obtenidas. Por contra, los algoritmos de extracci\'on de caracter\'isticas son aquellos que crean nuevas caracter\'isticas a partir de transformaciones y/o combinaciones de las caracter\'isticas del conjunto original. 

Algunos m\'etodos, como por ejemplo el an\'alisis de componentes principales
(PCA), permite transformar las caracter\'isticas originales en un nuevo conjunto de caracter\'isticas. En este sentido, PCA es un m\'etodo de extracci\'on de caracter\'isticas.

Sin embargo, esta t\'ecnica tambi\'en permite escoger del nuevo conjunto de caracter\'isticas, aquellas que aportan mayor informaci\'on. En este trabajo se ha utilizado
PCA para conseguir un mejor y m\'as reducido conjunto de caracter\'isticas.


\subsection{An\'alisis en componentes principales (PCA)}

%PEDIR .tex



